// https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/?envType=study-plan-v2&envId=top-interview-150

// 辅助函数和主函数由AI生成

// 算法思路总结：
// 1. 使用层序遍历思想，利用已建立的next指针
// 2. 为下一层创建虚拟节点，避免内存分配
// 3. 遍历当前层时连接下一层的左右子节点
// 4. 移动头指针到下一层继续处理
// 5. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

struct Node
{
    int val;
    Node *left;
    Node *right;
    Node *next;
    Node(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

class Solution
{
public:
    Node *connect(Node *root)
    {
        if (root == NULL)
            return NULL;

        Node *head = root;
        while (head != NULL)
        {
            Node dummy = Node(-1);
            Node *tail = &dummy;
            for (Node *cur = head; cur != NULL; cur = cur->next)
            {
                if (cur->left != NULL)
                {
                    tail->next = cur->left;
                    tail = tail->next;
                }
                if (cur->right != NULL)
                {
                    tail->next = cur->right;
                    tail = tail->next;
                }
            }
            head = dummy.next;
        }

        return root;
    }
};

Node *createTestTree1()
{
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(7);
    return root;
}

void printNextConnections(Node *root)
{
    Node *levelStart = root;

    while (levelStart)
    {
        Node* curr = levelStart;
        while (curr)
        {
            cout << curr->val;
            curr->next ? cout << " -> " : cout << " -> NULL";
            curr = curr->next;
        }
        cout << endl;

        curr = levelStart;
        levelStart = nullptr;
        while (curr && !levelStart)
        {
            if (curr->left)
            {
                levelStart = curr->left;
            }
            else if (curr->right)
            {
                levelStart = curr->right;
            }
            curr = curr->next;
        }
    }
}

void deleteTree(Node *root)
{
    if (root == NULL)
        return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main()
{
    Solution solution;

    cout << "测试用例1: [1,2,3,4,5,null,7]" << endl;
    Node *root1 = createTestTree1();
    Node *result1 = solution.connect(root1);
    printNextConnections(result1);
    deleteTree(root1);
    cout << endl;

    cout << "测试用例2: []" << endl;
    Node *root2 = NULL;
    Node *result2 = solution.connect(root2);
    if (result2 == NULL)
    {
        cout << "空树返回NULL" << endl;
    }
    cout << endl;

    return 0;
}